/**
 * @author LKQ
 * @date 2022/2/17 11:04
 * @description 回溯
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.findTargetSumWays(new int[]{1}, 1);
    }
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    /**
     * 回溯函数
     * @param nums 已知数组
     * @param target 目标和
     * @param index 数组下标
     * @param sum 总和
     */
    private void backtrack(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        }else {
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }

}
